The present invention relates, in general, to the field of microprocessor design and the issuance of memory instructions therefor. More particularly, the present invention relates to a system, apparatus and method for maintaining program correctness while allowing loads to be boosted past stores in an out-of-order machine.
Early computer processors (also called microprocessors) included a central processing unit or instruction execution unit that executed only one instruction at a time. As used herein the term processor includes complete instruction set computers ("CISC"), reduced instruction set computers ("RISC") and hybrids. In response to the need for improved performance several techniques have been used to extend the capabilities of these early processors including pipelining, superpipelining, superscaling, speculative instruction execution, and out-of-order instruction execution.
Pipelined architectures break the execution of instructions into a number of stages where each stage corresponds to one step in the execution of the instruction. Pipelined designs increase the rate at which instructions can be executed by allowing a new instruction to begin execution before a previous instruction is finished executing. Pipelined architectures have been extended to "superpipelined" or "extended pipeline" architectures where each execution pipeline is broken down into even smaller stages (i.e., microinstruction granularity is increased). Superpipelining increases the number of instructions that can be executed in the pipeline at any given time.
"Superscalar" processors generally refer to a class of microprocessor architectures that include multiple pipelines that process instructions in parallel. Superscalar processors typically execute more than one instruction per clock cycle, on average. Superscalar processors allow parallel instruction execution in two or more instruction execution pipelines. The number of instructions that may be processed is increased due to parallel execution. Each of the execution pipelines may have differing number of stages. Some of the pipelines may be optimized for specialized functions such as integer operations or floating point operations, and in some cases execution pipelines are optimized for processing graphic, multimedia, or complex math instructions.
The goal of superscalar and superpipeline processors is to execute multiple instructions per cycle ("IPC"). Instruction-level parallelism ("ILP") available in programs can be exploited to realize this goal, however, this potential parallelism requires that instructions be dispatched for execution at a sufficient rate. Conditional branching instructions create a problem for instruction fetching because the instruction fetch unit ("IFU") cannot know with certainty which instructions to fetch until the conditional branch instruction is resolved. Also, when a branch is detected, the target address of the instructions following the branch must be predicted to supply those instructions for execution.
Recent processor architectures use a branch prediction unit to predict the outcome of branch instructions allowing the fetch unit to fetch subsequent instructions according to the predicted outcome. Branch prediction techniques are known that can predict branch outcomes with greater than 95% accuracy. These instructions are "speculatively executed" to allow the processor to make forward progress during the time the branch instruction is resolved. When the prediction is correct, the results of the speculative execution can be used as correct results, greatly improving processor speed and efficiency. When the prediction is incorrect, the completely or partially executed instructions must be flushed from the processor and execution of the correct branch initiated.
Early processors executed instructions in an order determined by the compiled machine-language program running on the processor and so are referred to as "in-order" or "sequential" processors. In superscalar processors multiple pipelines can simultaneously process instructions only when there are no data dependencies between the instructions in each pipeline. Data dependencies cause one or more pipelines to "stall" waiting for the dependent data to become available. This is further complicated in superpipelined processors where, because many instructions are executed simultaneously in each pipeline, the potential quantity of data dependencies is large. Hence, greater parallelism and higher performance are achieved by "out-of-order" processors that include multiple pipelines in which instructions are processed in parallel in any efficient order that takes advantage of opportunities for parallel processing that may be provided by the instruction code.
Although out-of-order processing greatly improves throughput, it also increases complexity as compared to simple sequential processors. In fact, due to out-of-order instruction scheduling, a load instruction may be boosted past an older store which stores data to the same location. In this case, the load may hit in the cache and return an older value. Such cases need to be detected and corrected to ensure correct program execution.
Because of this, conventional process design simply allowed for memory instructions to be issued in order so that they can resolve in order. Nevertheless, in those instances where register space is unavailable and program code issues a store to a certain memory location instead (i.e. "register spilling")and then loads from the same location it is possible that the program compiler may not be able to determine that the store and load would map to the same memory location. This is referred to as a lack of memory disambiguation or lack of knowledge as to how the program addresses itself with what is actually mapped. Stated another way, the memory location map was constructed without knowledge that the store and load instructions were directed to the same memory location.
In out-of-order instruction execution, memory instructions may be issued in any order, including loads and stores. While it is possible to dispatch instructions other than loads and stores out of order while maintaining in order execution of these instructions, such is a clearly less than optimal solution. A need therefore exists for scheduling load and store instructions without knowledge of their addresses. Particularly, it is necessary to organize the out-of-order execution such that loads which occur either before or after a store produce a coherent result and that data is not utilized from a cache location that is older than the data that is being stored into it.